package 剑指offer.树;

import java.util.Arrays;

/**
 * 给出先序遍历以及中序遍历
 * 要求把二叉树构建出来
 *
 * 前序遍历 DLR 时每遇到一个节点就输出
 * 中序遍历 LDR ，通过根节点可以把左右子树分开
 */
public class 第7题重建二叉树 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public static TreeNode reBuildBinaryTree(int[] pre, int[] middle) {
        if (pre == null || middle == null || pre.length == 0 || middle.length == 0) {
            return null;
        }
        // 首先通过 pre 找到根节点
        TreeNode root = new TreeNode(pre[0]);
        // 然后在 middle 里面划分根节点左右的数据，它左边的是左子树，右边的是右子树
        for (int i = 0; i < pre.length; i++) {
            if (pre[0] == middle[i]) {// 在 middle 到了一个根节点
                // 然后就将原来的两个遍历结果数组切分，分给左右子树，递归函数会一直找到叶子节点上，自动组装各个节点
                root.left = reBuildBinaryTree(Arrays.copyOfRange(pre, 1, i + 1),
                        Arrays.copyOfRange(middle, 0, i));
                root.right = reBuildBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length),
                        Arrays.copyOfRange(middle, i + 1, middle.length));
            }
        }
        return root;
    }

    public static void main(String[] args) {
        int[] pre = {10, 6, 4, 8, 14, 12, 16};
        int[] middle = {4, 6, 8, 10, 12, 14, 16};
        TreeNode tree = reBuildBinaryTree(pre, middle);
        // 预期答案： 4 8 6 12 16 14 10
        postOrderRe(tree);
    }

    // 后序遍历递归实现
    public static void postOrderRe(TreeNode tree) {
        if (tree == null)
            return;
        else {
            postOrderRe(tree.left);
            postOrderRe(tree.right);
            System.out.print(tree.val + " ");
        }
    }
}
